package solutions.leetcode.hard;

import java.util.Arrays;

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/largest-multiple-of-three/">1363. 形成三的最大倍数</a>
 */
public class Solution1363 {
    public String largestMultipleOfThree(int[] digits) {
        int[] count = new int[10];
        int sum = 0;
        for (int item : digits) {
            count[item]++;
            sum += item;
        }
        if (sum % 3 == 1) {
            if (!delete(count, 1, 1)) {
                delete(count, 2, 2);
            }
        } else if (sum % 3 == 2) {
            if (!delete(count, 2, 1)) {
                delete(count, 1, 2);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >=0; i--) {
            while (count[i]-- > 0) {
                sb.append(i);
            }
        }

        if (sb.length() == 0) {
            return "";
        } else if (sb.charAt(0) == '0') {
            return "0";
        } else {
            return sb.toString();
        }
    }

    boolean delete(int[] count, int mod, int time) {
        for (int i = mod; i < count.length && time > 0;) {
            if (count[i] > 0) {
                count[i]--;
                time--;
            } else  {
                i += 3;
            }
        }
        return time == 0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1363().largestMultipleOfThree(new int[]{
                5, 8
        }));
    }
}
